//
// Created by Administrator on 2021/4/5.
//
/*给你两个有序整数数组nums1 和 nums2，请你将 nums2 合并到nums1中，使 nums1 成为一个有序数组。

初始化nums1 和 nums2 的元素数量分别为m 和 n 。你可以假设nums1 的空间大小等于m + n，这样它就有足够的空间保存来自 nums2 的元素。

示例 1：
输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]

示例 2：
输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]

提示：
nums1.length == m + n
nums2.length == n
0 <= m, n <= 200
1 <= m + n <= 200
-109 <= nums1[i], nums2[i] <= 109

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

class Solution {
public:
    static void merge(vector<int> &nums1, int m, vector<int> &nums2, int n) { // 两个数组合并后排序 没有用到有序数组的性质
        for (int i = 0; i < n; ++i) {
            nums1[i + m] = nums2[i];
        }
        sort(nums1.begin(), nums1.end());
    }
};

class Solution2 {
public:
    static void merge(vector<int> &nums1, int m, vector<int> &nums2, int n) {
        int p1 = 0, p2 = 0;
        int sorted[m + n]; // 保存中间结果
        int cur;
        while (p1 < m || p2 < n) {
            if (p1 == m) {
                cur = nums2[p2++];
            } else if (p2 == n) {
                cur = nums1[p1++];
            } else if (nums1[p1] < nums2[p2]) {
                cur = nums1[p1++];
            } else {
                cur = nums2[p2++];
            }
            sorted[p1 + p2 - 1] = cur;
        }
        for (int i = 0; i != m + n; ++i) { // 结果复制到nums1中
            nums1[i] = sorted[i];
        }
    }
};

class Solution3 {
public:
    static void merge(vector<int> &nums1, int m, vector<int> &nums2, int n) { // 从后边开始 原位
//        int p1 = m - 1, p2 = n - 1;
//        int tail = m + n - 1;
//        int cur;
//        while (p1 >= 0 || p2 >= 0) {
//            if (p1 == -1)
//                cur = nums2[p2--];
//            else if (p2 == -1)
//                cur = nums1[p1--];
//            else if (nums1[p1] > nums2[p2])
//                cur = nums1[p1--];
//            else
//                cur = nums2[p2--];
//            nums1[tail--] = cur;
//        }
        int i = m - 1, j = n - 1; // 初始指针分别指向两个数组的末尾
        int tail = m + n - 1; // nums1的尾部指针
        int cur; // 临时变量
        while (i >= 0 or j >= 0) {
            if (i == -1) { // 第一个指针已经到头
                cur = nums2[j--];
            } else if (j == -1) {
                cur = nums1[i--];
            } else if (nums1[i] > nums2[j]) {
                cur = nums1[i--];
            } else {
                cur = nums2[j--];
            }
            nums1[tail--] = cur; // 将得到的值放入nums1的尾部
        }
    }
};

class Solution4 {
public:
    static void merge(vector<int> &nums1, int m, vector<int> &nums2, int n) { // 优秀题解
        nums1.resize(m);
        int i = 0, j = 0;
        while (j < n && i < m) {
            if (nums1[i] > nums2[j]) {
                nums1.insert(nums1.begin() + i, nums2[j++]); // 把nums2中小于当前nums1的放入
                m++;
            }
            i++;
        }
        while (j < n) {
            nums1.push_back(nums2[j++]); // 把nums2中剩下的放入
        }
    }
};

int main() {
    vector<int> nums1 = {1, 2, 3, 7, 0, 0};
    vector<int> nums2 = {2, 5, 6};
//    Solution::merge(nums1, 4, nums2, 3);
//    Solution2::merge(nums1, 4, nums2, 3);
//    Solution3::merge(nums1, 4, nums2, 3);
    Solution4::merge(nums1, 4, nums2, 3);

    for (int i : nums1) {
        cout << i << endl;
    }
    return 0;
}